public class LCS {
    public String LCS (String s1, String s2) {
        // write code here
        s1 = " " + s1;
        s2 = " " + s2;
        // dp[i][j]表示s1字符串以第i个位置为结尾的和s2字符串以第j个位置为结尾的最长公共子序列
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        String[][] dp = new String[s1.length()][s2.length()];
        for (int i = 0; i < s1.length(); i++) {
            dp[i][0] = "";
        }
        for (int j = 0; j < s2.length(); j++) {
            dp[0][j] = "";
        }
        String ret = "";
        for (int i = 1; i < s1.length(); i++) {
            for (int j = 1; j < s2.length(); j++) {
                if (c1[i] == c2[j]) {
                    dp[i][j] = dp[i-1][j-1] + c1[i];
                } else {
                    if (dp[i-1][j].length() > dp[i][j-1].length()) {
                        dp[i][j] = dp[i-1][j];
                    } else {
                        dp[i][j] = dp[i][j-1];
                    }
                }
                if (dp[i][j].length() > ret.length()) {
                    ret = dp[i][j];
                }
            }
        }
        return "".equals(ret) ? "-1" : ret;
    }

    public static void main(String[] args) {
        LCS lcs = new LCS();
        System.out.println(lcs.LCS("abc",""));
    }
}
